package 笔试;
class Node{
    int val;
    Node next;
    public Node(int val){
        this.val=val;
    }
}
public class Main1 {
    Node sortList(Node head) {
        return head==null?null:mergeList(head);

    }
    Node mergeList(Node head){
        if(head.next==null) return head;
        Node slow,fast,pre;
        slow=fast=head;
        pre=null;
        //求出中点
        while (fast!=null&&fast.next!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next.next;
        }
        pre.next=null;
        //进行分解，直到分解到一个节点为止
        Node left=mergeList(head);
        Node right=mergeList(slow);
        return merge(left,right);
    }
    Node merge(Node left,Node right){

        Node dummy=new Node(-1);
        Node cur=dummy;
        while (left!=null&&right!=null){
            if(left.val<right.val){
                cur.next=left;
                left=left.next;
            }else {
                cur.next=right;
                right=right.next;
            }
            cur=cur.next;
        }
        if(left!=null){
            cur.next=left;
        }
        if(right!=null){
            cur.next=right;
        }
        return dummy.next;
    }

    static int get(int num){
        int res=0;
        while (num>0){
            res+=num;

            num--;
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(get(2));
    }
}




